perm filename 04[NSF,BGB] blob
sn#073917 filedate 1973-11-29 generic text, type T, neo UTF8
DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT
RESEARCH PROPOSAL SUBMITTED TO WALTER E. DISNEY ENTERPRISES
BY
Computer Science Department
School of Humanities and Sciences
Stanford University
IN
COMPUTER-AIDED ANIMATION OF THREE-DIMENSIONAL OBJECTS
Co-Principal Investigators:
JOHN McCARTHY
Professor of Computer Science
BRUCE BAUMGART
Research Associate in Computer Science
This is a new request
The desired starting date is January 1, 1974.
The total amount requested for 24 months is $ 214,881
ABSTRACT:
This is a request for a grant of $ 214,881 to support a two
year reseach program in computer aided animation of three
dimensional objects. Existing computer graphics and design
technology is reviewed and new ideas are presented. Specific ideas
developed concern 3-D representation, 3-D acquistion, and language
extensions for geometric modeling. The competence of the authors is
advertised; the facilities of the Stanford Artificial Intelligence
Project are outlined; and a budget and work plan are submitted.
CONTENTS:
1. IDEAS AND WORK ALREADY DONE
2. WHAT WE PROPOSE TO DO
3. PREVIOUS WORK AT STANFORD
4. RELATION TO WORK DONE ELSEWHERE
5. FACILITIES AT STANFORD A.I. LAB
6. BIOGRAPHIES
7. BIBLIOGRAPHY
8. BUDGET
1. IDEAS AND WORK ALREADY DONE.
The proposed work is based on the following ideas and work
already done:
i. Explicit 3-D Object Representation.
An effective way of obtaining 2-D drawings of a
three-dimensional object is to derive the drawings from an explicit
computer model of the three-dimensional object. Sequences of
perspective drawings of the object are obtained automatically from
the three-dimensional description, with the hidden surfaces of the
object removed and appropriate shading and coloring provided.
ii. Object Generation from Physical Description.
A convenient way of making an explicit computer model of an
object is to simulate the process of building the object. That is,
the description of how to build an object is an implicit
representation of the object. For example it is easier to describe
Figure 2 as a dodecahedron with a regular five pointed star shaped
hole cut through it, than it is to draw the figure with a light pen
or to list the loci of its vertices.
iii. Language Extension.
Rather than developing new languages for geometric modeling
and mechanical drawing, we believe it is best to extend the old
languages: FORTRAN, ALGOL and LISP. The elements of language
extension include new data types for the language, general low
level primitives for manipulating the new data types, and a
convenient set of higher level operations. The division of the work
into high level operations defined in terms of low level primitives
is an important part of the design because it isolates the data
structure manipulating code.
iv. Object Representation from Physical Measurement,
Another way to get an explicit computer model of an object
is to derive it from measurements made on an actual physical object,
2-D drawing, or picture. For example, the physical object might be a
clay model of the thing being designed. We believe that only the
lack of appropriate software is preventing the use of television
cameras as an inexpensive, accurate, and automatic means of entering
graphical data into a computer. (Figure 3)
v. Prejudice against Pens for Interactive Graphics Control.
It has been our recent experience that a distinction should
be made between using a light pen (or sonic pen, Rand tablet, etc.)
for graphics input and using it for graphics editing and control. We
observe that when adequate keyboard edit, control and language
conventions are provided the use of the light pen diminishes to the
point where it is only demonstrated to visitors who expect graphics
to involve light pens. One reason for this is that when an operator
can do something exactly in a few keystrokes he does not bother with
picking up the pen, acquiring the pen tracker, and drawing. A second
reason is that a pen is necessarily based on 2-D screen coordinates
in which overlapping portions of a 3-D drawing can not be directly
distinguished with a light pen. Pen based editing systems require a
keyboard or button box in any event, so we argue that an operator
who can control and alter a drawing with his hands always in the
locality of the keyboard will be more efficient than an operator who
has to use both a keyboard and a pen. However, the use of a pen (or
Rand Tablet) for graphics input, such as tracing chromosome
photographs into the computer, is justifiable and expedient but not
directly relevant to editing a 3-D design. That is, pens
are functionally replaceable by either TV cameras or keyboards.
vi. Mechanical Simulation.
Information, such as the degrees of freedom of motion, is
included in the object description and can be used to get pictures
of objects in different positions. This is demonstrated in the
enclosed flip book animation of a mechanical arm turning a block
over.
vii. Photometric Simulation.
Photometric information such as the location and nature of
light sources and the light scattering properties of the objects'
surfaces can be included in the model and used to compute the actual
appearance of solid opaque objects. (Figure 4)
2. WHAT WE PROPOSE TO DO.
We propose to represent and simulate solid objects in a
computer for the sake of animation and script design.
Our two year goal will be to automate as much as possible the task
of creating and altering three-dimensional data structures from
which color film can be derived. The overall project to
date has been called "geometric modeling" a term which we use to
refer to our particular combination of computer graphics, physical
world modeling, image processing and geometry. Accordingly, the
details of the work we propose doing will be presented in terms of
the elements comprising a Geometric Modeling System.
Like a computer, the four main elements of a geometric
modeling system are memory, process, input and output. Starting with
memory, there are the problems of representation (how to describe a
physical object), accessing (how to find a particular description by
name, by location, or by whether it is currently in view), and
efficiency (how to keep the size of storage space down and how to
dynamically allocate fast and slow memory resources).
The presently implemented explicit object representation is
based on polyhedron models of solid rigid objects. A simple object
called a body is defined by a surface shell composed of vertices,
edges and faces that satisfy the Euler equation, V - E + F = 2.
Such polyhedron bodies are combined to form compound objects. At
present, curved objects are represented by approximating them using
a polyhedron composed of a sufficient number of flat polygonal
faces. We propose to further develop the appearance of curved
objects by automating the assignment of polygonal facets to a given
curved surface. Other current representation problems that we
propose working on include constructing efficient (and compatible)
object labelling, handling mechanical properties of an object, and
better representing compound and flexible objects.
A final representation issue we would study is that of a
format for communication of three-dimensional models between
modeling systems. Although we believe that it is too early to
propose a standard format, it is desirable to design and promulgate
a format as simple, but as inclusive as possible; it is also
desirable to develop formatible I/O routines so that new formats
can be sent or received.
The usual input devices to a geometric modeling system
include keyboards, light-pens, joy-sticks, buttons, cameras and
film scanners, of which the most important to this proposal is the
keyboard, because it is currently the best device for language input.
Indeed, we believe that we can demonstrate that a system based on
keyboards can do geometric control and editing better than a system
based on both a light pen and a keyboard. With respect to language,
we are proposing two projects: first, we would extend the programming
languages FORTRAN, ALGOL and LISP and second, we would continue
to develop our interactive edit and control language. The elements
of a language extension include new data types (the "memory" of our
system), a micro language of primitive operations and a macro
language of more complex operations.
The micro language is composed of a small set of primitive
functions that invoke the only subroutines allowed to directly
create and alter the data structure. All the geometric processors,
editors, input, output and higher language operations are
implemented in terms of these fewer than fifty primitives. The
reason for having a two-level system is to isolate and minimize the
amount of code that is necessarily dependent on the implementation
details of the particular higher level language. Furthermore, it is
possible to construct primitives that are complete and general with
respect to fundamental principles in polyhedron topology and
geometry. For example, we now have a set of Euler primitives that
can generate any Eulerian polyhedron (and only Eulerian polyhedra)
as well as a set of Euclidean primitives for applying the group of
Euclidean transformations. With more good luck, we intend to
isolate sets of primitives for mechanics and for image formation.
The macro level of language extension is comprised of
operations that make it convenient to simulate building a mechanical
model of an object. The present macro level includes an operation
for "sweeping" edges into faces, and faces into solids; an
operation for "glueing" surfaces together; an operation for passing
"cutting" planes thru an object; and a most powerful trio of
operations for forming the volume union, intersection and
difference of two given polyhedra. Since polyhedra can be taken as
either bounding a finite solid volume or a finite empty volume, we
have found it convenient to draw some objects indirectly by building
their holes and intersecting the holes with their simple outer
shape. Further macro operations we propose to code would include
more "imaginary" ones for bending, constraining, filling,
enveloping, and expanding upon a skeleton; as well as some more
"realistic" operations that would model regular machine shop tools
such as a lathe, punch and milling machine; as well as machine
building processes such as welding, fastening and assembly.
Our second language project is oriented towards edit and
control. The main differences between an interactive graphics
editor and a graphics programming language are that an editor
carries along its working context so that most arguments and data do
not have to be explicitly named (because they happen to be "at the
top of the stack") and that they are visibly intensified or
otherwise indicated on the display screen. The advantage of the
interactive editor is that the user is relieved of having to coin
and call names of things. However, the disadvantage is that he
cannot develop subroutines of the power available in a programming
language, which provides notation for procedures, arguments, and
variables. We plan to keep the programming language level distinct
from the control and edit language level; although it should be
clear that both language levels are calling the same primitive
execution routines.
Besides language inputs, a geometric modeling system should
have a way of reading data that is already in graphical form. For
such input, we propose using a television camera. For example, we
already have developed video intensity contouring to rapidly provide
the edges of an image in a form available for graphics editing.
Although video input per se is of secondary importance to this
proposal, we happen to have such hardware and software available at
Stanford and can make good use of it with little additional effort.
Furthermore, video (or visual) computer input has considerable
promise as a major input device of future computers.
The third element of a geometric modeling system is its
(software) processors. There are language processors, mechanical
simulators, locus solvers, image analysis and image synthesis, as
well as that process, quite central to three-dimensional drawing,
which is hidden line (and surface) elimination. We have a hidden
line eliminator which combines several of the existing techniques
and which can generate both line drawings and video images; also we
have reason to believe that further work on our design will yield a
hidden eliminator that can handle apparently curved objects,
generate shadows, use the coherence between successive images, and
still be fast without special purpose hardware. Since the purpose
of the processors just mentioned should be sufficiently clear, we
shall skip detailing their algorithms and implementation, although
this will comprise the bulk of the work and publication we propose
to do.
The fourth and final element of our modeling system is the
output, which includes dynamic CRT display, video display,
hardcopy printing, and magnetic tape. Although mundane, the
numerical object descriptions on conventional (nondisplay) computer
media like magnetic tape is important in making the output of an
interactive display system available for further automatic
processing or communication. On the other hand, a high quality CRT
that can display characters and vectors is now and shall remain the
primary tool requisite to developing interactive graphics software.
Consequently, nearly a third of the budget included with this
proposal is allocated to aquiring such a CRT to enhance our existing
display system. The most promising alternative to a CRT is a video
display. However, present day video display systems would require a
very large computer and fast memory to achieve the resolution and
speed of a CRT display.
Management Plan
The single focus of responsibility for management of this
research proposal is the senor principal investigator, John
McCarthy, professor of Computer Science, Stanford University.
Ignoring the overall system organization and fine details, the goals
of the proposed project are summarized in the following list:
Items partially in hand, but requiring first year work:
1. Representation of solid rigid three-dimensional polyhedra.
2. Language extension of geometric primitives.
3. Language extension of object building operations.
4. A hidden line (and surface) eliminator.
5. A geometric editor.
Second year items:
6. A Script action language compiler.
7. Generation of high quality color video from geometric models.
8. Representation for the "appearance" of curved objects.
9. Representation for flexible objects.
10. Video acquisition of physical objects and 2-D artist drawings.
11. Mechanical simulation: gravity, inertia tensors, collisions.
12. Photometric simulation - shadows, multiple light sources.
Since substantial work has already been done on items one
through five, they would be included in the most conservative
estimate of our potential achievements over the next two years.
Intermediate expectations include making considerable progress and
original contribution with respect to items one through ten, as well
as beginning work on the two kinds of simulators, items 11 amd 12. An
optimistic expectation would be to finish everything.